package SwordForOffer.Problem34;

import java.util.Arrays;
import java.util.Collections;

public class UglyNumber {
	/*
	 * 只包含因子2,3,5的数为丑数，1是第一个丑数，求从小到大的第1500个丑数
	 */
	public int getUglyNumber(int n)
	{
		if(n<0)
			return 0;
		int[] uglyArray=new int[n];
		uglyArray[0]=1;
		int multiply2=1;
		int multiply3=1;
		int multiply5=1;

		for(int i=1;i<uglyArray.length;i++)
		{
			int min=Min(multiply2*2,multiply3*3,multiply5*5);
			uglyArray[i]=min;
			while(multiply2*2<=min)
				multiply2++;
			while(multiply3*3<=min)
				multiply3++;
			while(multiply5*5<=min)
				multiply5++;
		}
		return uglyArray[n-1];
	}
	int Min(int number1,int number2,int number3)
	{
		int min=(number1<number2)?number1:number2;
		return min<number3?min:number3;
	}

	public int myGetUglyNumber(int n) {
		int[] uglyNum = new int[n];
		int[] multiply = {1,1,1};
		uglyNum[0] = 1;
		for (int i = 1; i < n ; i++){
			int min = Math.min(multiply[0] * 2,Math.min(multiply[1] * 3,multiply[2] * 5));
			uglyNum[i] = min;
			while (multiply[0]*2 <= min){
				multiply[0] ++;
			}
			while (multiply[1]*3 <= min){
				multiply[1] ++;
			}
			while (multiply[2]*5 <= min){
				multiply[2] ++;
			}

		}
		System.out.println(Arrays.toString(uglyNum));
		return uglyNum[n - 1];
	}
}
